/*
题目: 加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

https://leetcode.cn/problems/gas-station
 */
public class CanCompleteCircuit {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 环形路上的每个站点都有好人或者坏人, 从哪个起点出发, 能够完成环绕
        int n = gas.length, start = 0;
        int need = 0; // 完成全程的油量
        int cur = 0; // 当前的油量

        // 完成全程, 油($) 的多余或者缺少 情况
        for (int i = 0; i < n; i ++)
            need += gas[i] - cost[i];

        // 好人给的钱 < 坏人抢的钱
        if (need < 0)   return -1;

        // 否则说明: 必存在 以某点作为起点, 好人给的钱足以度过难关
        for (int i = 0; i < n; i ++) {
            cur += gas[i] - cost[i];

            // 如果上次那个起点 last 不足以到达这个地方
            // 那么说明 [last, i] 中选哪个作为起点都不足以到 i + 1, 因为最好的情况就是 last 收了钱, 但是还是过不去
            if (cur < 0) {
                start = i + 1;
                cur = 0;
            }
        }
        return start;
    }
}
